Introduction

In "solving linear congruences", we learned how to solve a single congruence such as $$ax \equiv b \pmod{n}.$$ But what if we have several congruences at the same time, all involving the same unknown number?

For example:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$
• $x \equiv 2 \pmod{7}$

Is there a number that satisfies all of them at once?

Surprisingly, when the moduli (the numbers after “mod”) are chosen well, there is always a solution, and that solution is unique up to a certain size. This remarkable fact is called the Chinese Remainder Theorem, named after ancient mathematicians in China who discovered it more than 1,500 years ago.

What a System of Congruences Is

A system of congruences is a collection of statements like: $$x \equiv a_1 \pmod{n_1}$$ $$x \equiv a_2 \pmod{n_2}$$ $$\dots$$ $$x \equiv a_k \pmod{n_k}.$$ Each congruence says that $x$ leaves a certain remainder when divided by a certain number.

The goal is to find a single number $x$ that satisfies all of them.

Sometimes this is easy.
Sometimes it seems impossible.
The Chinese Remainder Theorem tells us exactly when it is possible.

When a System Has a Solution

The key condition is simple:

A system of congruences has a solution if all the moduli are pairwise coprime.

This means:

• Any two moduli share no common factors except $1$.
• For example, $3$, $5$, and $7$ are pairwise coprime.
• But $4$ and $6$ are not, because they share a factor of $2$.

If the moduli are pairwise coprime, then:

• A solution exists.
• The solution is unique modulo the product of all the moduli.

Example:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$

Since $3$ and $5$ are coprime, a solution exists, and it is unique modulo $15$.

Why Solutions Are Unique

If the moduli are pairwise coprime, then the product $$N = n_1 n_2 \cdots n_k$$ acts like a “master modulus.”

The Chinese Remainder Theorem says:

• There is exactly one solution modulo $N$.
• All other solutions differ from it by multiples of $N$.

This means that once you find one solution, you have found them all.

Example:

If a system has a unique solution modulo $15$, then all solutions are: $$x = x_0 + 15k,$$ where $k$ is any whole number.

Solving Two Congruences by Inspection

Let’s start with the simplest case: $$x \equiv a \pmod{m}$$ $$x \equiv b \pmod{n}.$$ If $m$ and $n$ are coprime, we can often solve this by looking for a number that fits both patterns.

Example:

Solve:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$

List numbers that are $2$ mod $3$:

• $2, 5, 8, 11, 14, 17, \dots$

Now check which of these are $3$ mod $5$:

• $3, 8, 13, 18, \dots$

The first match is $8$.

So the solution is: $$x \equiv 8 \pmod{15}.$$ This method works well for small numbers.

Solving Two Congruences Using Multipliers

For larger numbers, inspection becomes slow.
A more systematic method uses the idea of multipliers.

Given: $$x \equiv a \pmod{m}$$ $$x \equiv b \pmod{n},$$ we want to build $x$ from pieces that “fit” each congruence.

Define:

• $M = mn$
• $M_m = M / m = n$
• $M_n = M / n = m$

We then find numbers:

• $y_m$ such that $M_m y_m \equiv 1 \pmod{m}$
• $y_n$ such that $M_n y_n \equiv 1 \pmod{n}$

These are just multiplicative inverses.

Then the solution is: $$x = a M_m y_m + b M_n y_n.$$ This looks complicated, but the steps are simple:

1. Compute $M_m$ and $M_n$.
2. Find their inverses modulo $m$ and $n$.
3. Combine everything.

We will see examples in the next section.

Solving Several Congruences Step by Step

Suppose we want to solve:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$
• $x \equiv 2 \pmod{7}$

Since $3$, $5$, and $7$ are pairwise coprime, a solution exists.

Step 1: Solve the first two

From earlier, we know:

• $x \equiv 8 \pmod{15}$

Step 2: Combine this with the third

Now solve:

• $x \equiv 8 \pmod{15}$
• $x \equiv 2 \pmod{7}$

List numbers that are $8$ mod $15$:

• $8, 23, 38, 53, 68, \dots$

Check which are $2$ mod $7$:

• $2, 9, 16, 23, 30, \dots$

The first match is $23$.

So the solution is: $$x \equiv 23 \pmod{105}.$$ This means all solutions are: $$x = 23 + 105k.$$

Solving Several Congruences Using Multiplicative Inverses

Now let’s solve the same system:

• $x \equiv 2 \pmod{3}$
• $x \equiv 3 \pmod{5}$
• $x \equiv 2 \pmod{7}$

using the general Chinese Remainder Theorem formula with multiplicative inverses.

Step 1: Compute the product of the moduli

The moduli are pairwise coprime, so we set $$N = 3 \cdot 5 \cdot 7 = 105.$$ For each congruence, define

• $N_1 = N / 3 = 35$
• $N_2 = N / 5 = 21$
• $N_3 = N / 7 = 15$

Step 2: Find the multiplicative inverses

We now find numbers $y_1, y_2, y_3$ such that

• $N_1 y_1 \equiv 1 \pmod{3}$
• $N_2 y_2 \equiv 1 \pmod{5}$
• $N_3 y_3 \equiv 1 \pmod{7})$

For $y_1$:

We need $35 y_1 \equiv 1 \pmod{3})$

Since $35 \equiv 2 \pmod{3}$, this is $$2 y_1 \equiv 1 \pmod{3}.$$ Trying small values: $y_1 = 2$ gives $2 \cdot 2 = 4 \equiv 1 \pmod{3}$, so $$y_1 = 2.$$

For $y_2$:

We need $21 y_2 \equiv 1 \pmod{5}$.

Since $21 \equiv 1 \pmod{5}$, this is $$1 \cdot y_2 \equiv 1 \pmod{5},$$ so $$y_2 = 1.$$

For $y_3$:

We need $15 y_3 \equiv 1 \pmod{7}$.

Since $15 \equiv 1 \pmod{7}$, this is $$1 \cdot y_3 \equiv 1 \pmod{7},$$ so $$y_3 = 1.$$

Step 3: Build the solution

The Chinese Remainder Theorem tells us that a solution is given by $$x = a_1 N_1 y_1 + a_2 N_2 y_2 + a_3 N_3 y_3,$$ where $a_1, a_2, a_3$ are the remainders:

• $a_1 = 2 \pmod {3}$
• $a_2 = 3 \pmod {5}$
• $a_3 = 2 \pmod {7}$.

So $$x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1.$$ Compute each term:

• $2 \cdot 35 \cdot 2 = 140$
• $3 \cdot 21 \cdot 1 = 63$
• $2 \cdot 15 \cdot 1 = 30$

so $$x = 140 + 63 + 30 = 233.$$ We now reduce $233$ modulo $N = 105$: $$233 - 2 \cdot 105 = 233 - 210 = 23.$$ So $$x \equiv 23 \pmod{105}.$$ This matches the solution we found earlier by combining congruences step by step:

• Final answer: $x \equiv 23 \pmod{105}$.

Why the Chinese Remainder Theorem Works (Gentle Explanation)

The key idea is that when the moduli are coprime, each congruence controls a different “aspect” of the number.

For example:

• Modulo $3$ tells you the remainder when dividing by $3$.
• Modulo $5$ tells you the remainder when dividing by $5$.

Since $3$ and $5$ share no factors, these two pieces of information do not interfere with each other.

It is like knowing:

• The hour on a 12-hour clock
• The minute on a 60-minute clock

These two pieces of information uniquely determine the time.

The Chinese Remainder Theorem says that the same idea works for any number of moduli, as long as they are pairwise coprime.

Calculator

Exercises

Solve each system of congruences or explain why no solution exists.

1. • $x \equiv 1 \pmod{3}$
   • $x \equiv 2 \pmod{5}$

   Solution

   $$x \equiv 1 \pmod{3}$$ $$x \equiv 2 \pmod{5}$$ List numbers that are $1$ mod $3$:

   • $1, 4, 7, 10, 13, 16, 19, \dots$

   List numbers that are $2$ mod $5$:

   • $2, 7, 12, 17, 22, \dots$

   The first common value is $7$.

   So the solution is:

   • $x \equiv 7 \pmod{15}$

   All solutions are $x = 7 + 15k$, where $k$ is any whole number.

   Answer: $x \equiv 7 \pmod{15}$.

2. • $x \equiv 2 \pmod{4}$
   • $x \equiv 3 \pmod{6}$

   Solution

   $$x \equiv 2 \pmod{4}$$ $$x \equiv 3 \pmod{6}$$ First, check if this is consistent.

   List numbers that are $2$ mod $4$:

   • $2, 6, 10, 14, 18, \dots$

   List numbers that are $3$ mod $6$:

   • $3, 9, 15, 21, \dots$

   There is no overlap in these lists.

   Another way: any number that is $2$ mod $4$ is even, but any number that is $3$ mod $6$ is odd. So no number can satisfy both.

   Answer: No solution.

3. • $x \equiv 3 \pmod{7}$
   • $x \equiv 4 \pmod{9}$

   Solution

   $$x \equiv 3 \pmod{7}$$ $$x \equiv 4 \pmod{9}$$ List numbers that are $3$ mod $7$:

   • $3, 10, 17, 24, 31, 38, 45, 52, \dots$

   List numbers that are $4$ mod $9$:

   • $4, 13, 22, 31, 40, 49, \dots$

   The first common value is $31$.

   The moduli are $7$ and $9$, which are coprime, so the solution is unique modulo $7 \cdot 9 = 63$.

   So:

   • $$x \equiv 31 \pmod{63}$$

   All solutions are $x = 31 + 63k$.

   Answer: $x \equiv 31 \pmod{63}$.

4. • $x \equiv 2 \pmod{5}$
   • $x \equiv 3 \pmod{7}$
   • $x \equiv 1 \pmod{3}$

   Solution

   $$x \equiv 2 \pmod{5}$$ $$x \equiv 3 \pmod{7}$$ $$x \equiv 1 \pmod{3}$$ First, combine two at a time.

   Step 1: Combine mod $5$ and mod $7$

   Solve:

   • $x \equiv 2 \pmod{5}$
   • $x \equiv 3 \pmod{7}$

   List numbers that are $2$ mod $5$:

   • $2, 7, 12, 17, 22, 27, 32, 37, \dots$

   Check which are $3$ mod $7$:

   • $3, 10, 17, 24, 31, 38, \dots$

   The first common value is $17$.

   So:

   • $x \equiv 17 \pmod{35}$.

   Step 2: Combine this with $x \equiv 1 \pmod{3}$

   Now solve:

   • $x \equiv 17 \pmod{35}$
   • $x \equiv 1 \pmod{3}$

   List numbers that are $17$ mod $35$:

   • $17, 52, 87, 122, \dots$

   Check which are $1$ mod $3$:

   Numbers that are $1$ mod $3$ look like $1, 4, 7, 10, \dots$
   Compute remainders of the above list mod $3$:

   • $17 \equiv 2 \pmod{3}$
   • $52 \equiv 1 \pmod{3}$

   So $52$ works.

   The moduli $35$ and $3$ are coprime, so the solution is unique modulo $35 \cdot 3 = 105$.

   So:

   • $x \equiv 52 \pmod{105}$

   All solutions are $x = 52 + 105k$.

   Answer: $x \equiv 52 \pmod{105}$.

5. • $x \equiv 4 \pmod{11}$
   • $x \equiv 5 \pmod{13}$

   Solution

   $$x \equiv 4 \pmod{11}$$ $$x \equiv 5 \pmod{13}$$ List numbers that are $4$ mod $11$:

   • $4, 15, 26, 37, 48, 59, 70, 81, 92, \dots$

   List numbers that are $5$ mod $13$:

   • $5, 18, 31, 44, 57, 70, 83, \dots$

   The first common value is $70$.

   The moduli $11$ and $13$ are coprime, so the solution is unique modulo $11 \cdot 13 = 143$.

   So:

   • $x \equiv 70 \pmod{143}$

   All solutions are $x = 70 + 143k$.

   Answer: $x \equiv 70 \pmod{143}$.

6. • $x \equiv 6 \pmod{8}$
   • $x \equiv 1 \pmod{3}$

   Solution

   $$x \equiv 6 \pmod{8}$$ $$x \equiv 1 \pmod{3}$$ List numbers that are $6$ mod $8$:

   • $6, 14, 22, 30, 38, 46, \dots$

   Check which are $1$ mod $3$:

   Numbers that are $1$ mod $3$: $1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, \dots$

   From the first list:

   • $6 \equiv 0 \pmod{3}$
   • $14 \equiv 2 \pmod{3}$
   • $22 \equiv 1 \pmod{3}$

   So $22$ works.

   The moduli $8$ and $3$ are coprime, so the solution is unique modulo $8 \cdot 3 = 24$.

   So:

   • $x \equiv 22 \pmod{24}$

   You could also write that as $x \equiv -2 \pmod{24}$, but for this book we can keep it as $22$.

   Answer: $x \equiv 22 \pmod{24}$.

7. • $x \equiv 0 \pmod{4}$
   • $x \equiv 1 \pmod{5}$
   • $x \equiv 2 \pmod{7}$

   Solution

   $$x \equiv 0 \pmod{4}$$ $$x \equiv 1 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$

   Step 1: Combine mod $4$ and mod $5$

   Solve:

   • $x \equiv 0 \pmod{4}$
   • $x \equiv 1 \pmod{5}$

   Numbers that are $0$ mod $4$:

   • $0, 4, 8, 12, 16, 20, 24, \dots$

   Numbers that are $1$ mod $5$:

   • $1, 6, 11, 16, 21, 26, \dots$

   The first common value is $16$.

   So:

   • $x \equiv 16 \pmod{20}$.

   Step 2: Combine with $x \equiv 2 \pmod{7}$

   Now solve:

   • $x \equiv 16 \pmod{20}$
   • $x \equiv 2 \pmod{7}$

   Numbers that are $16$ mod $20$:

   • $16, 36, 56, 76, 96, \dots$

   Check which are $2$ mod $7$:

   • $16 \equiv 2 \pmod{7}$

   So $16$ already works.

   The moduli $20$ and $7$ are coprime, so the solution is unique modulo $20 \cdot 7 = 140$.

   So:

   • $x \equiv 16 \pmod{140}$

   All solutions are $x = 16 + 140k$.

   Answer: $x \equiv 16 \pmod{140}$.

8. • $x \equiv 3 \pmod{10}$
   • $x \equiv 4 \pmod{9}$

   Solution

   $$x \equiv 3 \pmod{10}$$ $$x \equiv 4 \pmod{9}$$ Check if $10$ and $9$ are coprime: they are (common divisor is $1$).

   Numbers that are $3$ mod $10$:

   • $3, 13, 23, 33, 43, 53, 63, 73, \dots$

   Numbers that are $4$ mod $9$:

   • $4, 13, 22, 31, 40, 49, 58, 67, \dots$

   The first common value is $13$.

   So:

   • $x \equiv 13 \pmod{90}$

   since $10 \cdot 9 = 90$ and the solution is unique modulo $90$.

   All solutions are $x = 13 + 90k$.

   Answer: $x \equiv 13 \pmod{90}$.

9. • $x \equiv 1 \pmod{6}$
   • $x \equiv 2 \pmod{7}$
   • $x \equiv 3 \pmod{8}$

   Solution

   $$x \equiv 1 \pmod{6}$$ $$x \equiv 2 \pmod{7}$$ $$x \equiv 3 \pmod{8}$$ The moduli $6$, $7$, and $8$ are pairwise coprime except that $6$ and $8$ share a factor $2$. So we need to be a bit careful, but we can still look for a common solution directly.

   Step 1: Combine mod $6$ and mod $7$

   Solve:

   • $x \equiv 1 \pmod{6}$
   • $x \equiv 2 \pmod{7}$

   Numbers that are $1$ mod $6$:

   • $1, 7, 13, 19, 25, 31, 37, 43, \dots$

   Numbers that are $2$ mod $7$:

   • $2, 9, 16, 23, 30, 37, 44, \dots$

   The first common value is $37$.

   So:

   • $x \equiv 37 \pmod{42}$

   since $\text{lcm}(6,7) = 42$.

   Step 2: Combine with $x \equiv 3 \pmod{8}$

   Now solve:

   • $x \equiv 37 \pmod{42}$
   • $x \equiv 3 \pmod{8}$

   Numbers that are $37$ mod $42$:

   • $37, 79, 121, 163, \dots$

   Check which are $3$ mod $8$:

   • $37 \equiv 5 \pmod{8}$
   • $79 \equiv 7 \pmod{8}$
   • $121 \equiv 1 \pmod{8}$
   • $163 \equiv 3 \pmod{8}$

   So $163$ works.

   We now have a common solution $x = 163$.

   To describe all solutions properly, we can take the least common multiple of $6$, $7$, and $8$:

   • $\text{lcm}(6,7,8) = 168$.

   So all solutions are:

   • $x \equiv 163 \pmod{168}$

   Answer: $x \equiv 163 \pmod{168}$.

10. • $x \equiv 5 \pmod{12}$
    • $x \equiv 7 \pmod{25}$

    Solution

    $$x \equiv 5 \pmod{12}$$ $$x \equiv 7 \pmod{25}$$ Check that $12$ and $25$ are coprime: they are.

    Numbers that are $5$ mod $12$:

    • $5, 17, 29, 41, 53, 65, 77, 89, 101, \dots$

    Numbers that are $7$ mod $25$:

    • $7, 32, 57, 82, 107, 132, \dots$

    Look for a common value.

    From the first list:

    • $5, 17, 29, 41, 53, 65, 77, 89, 101, 113, 125, 137, 149, 161, \dots$

    From the second list:

    • $7, 32, 57, 82, 107, 132, 157, 182, \dots$

    Check overlaps:

    • $5$ (no)
    • $17$ (no)
    • $29$ (no)
    • $41$ (no)
    • $53$ (no)
    • $65$ (no)
    • $77$ (no)
    • $89$ (no)
    • $101$ (no)
    • $113$ (no)
    • $125$ (no)
    • $137$ (no)
    • $149$ (no)
    • $161$ (no)
    • Continue: $173, 185, 197, 209, \dots$

    Notice $185$:

    • $185 \div 12$ leaves remainder $5$ (since $12 \cdot 15 = 180$),
    • $185 \div 25$ leaves remainder $10$ (so not $7$).

    Instead, use a more direct way.

    Write numbers that are $7$ mod $25$ and check mod $12$:

    • $7 \equiv 7 \pmod{12}$
    • $32 \equiv 8 \pmod{12}$
    • $57 \equiv 9 \pmod{12}$
    • $82 \equiv 10 \pmod{12}$
    • $107 \equiv 11 \pmod{12}$
    • $132 \equiv 0 \pmod{12}$
    • $157 \equiv 1 \pmod{12}$
    • $182 \equiv 2 \pmod{12}$
    • $207 \equiv 3 \pmod{12}$
    • $232 \equiv 4 \pmod{12}$
    • $257 \equiv 5 \pmod{12}$

    So $257$ is:

    • $257 \equiv 5 \pmod{12}$
    • $257 \equiv 7 \pmod{25}$

    So $257$ is a solution.

    The moduli $12$ and $25$ are coprime, so the solution is unique modulo $12 \cdot 25 = 300$.

    So:

    • $x \equiv 257 \pmod{300}$

    All solutions are $x = 257 + 300k$.

    Answer: $x \equiv 257 \pmod{300}$.